#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 4e4 + 5;
const int MOD = 999911659;

ll n, q;
ll b[4] = {2, 3, 4679, 35617};
ll a[4];
ll p;
ll fac[N], inv[N];

ll extgcd(ll a, ll b, ll& x, ll& y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  ll d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
void merge(int i) {
  ll m1 = b[i], m2 = b[i + 1];
  ll c1 = a[i], c2 = a[i + 1];
  ll x, y;
  // ? = k1 * m1 + c1 = k2 * m2 + c2;
  if (c1 > c2) swap(m1, m2), swap(c1, c2);
  ll c = c2 - c1;
  ll d = extgcd(m1, m2, x, y);
  if (c % d) exit(0);
  c /= d, m1 /= d, m2 /= d;
  // k1 = c * x + k * m2
  // k1 * m1 + c1 = k * m1 * m2 + c * x * m1 + c1
  y = m1 * m2;
  x = ((__int128_t)c * x % y * m1 % y + c1) % y;
  if (x < 0) x += y;
  a[i + 1] = x, b[i + 1] = y;
}
void extcrt() { rep(i, 0, 2) merge(i); }
ll fastpow(ll b, ll p, ll mod) {
  if (b % mod == 0) return 0;
  ll res = 1;
  while (p) {
    if (p & 1) res = res * b % mod;
    b = b * b % mod;
    p >>= 1;
  }
  return res;
}
void init() {
  fac[0] = 1;
  rep(i, 1, p - 1) fac[i] = fac[i - 1] * i % p;
  inv[p - 1] = fastpow(fac[p - 1], p - 2, p);
  per(i, p - 2, 0) inv[i] = inv[i + 1] * (i + 1) % p;
}
ll C(ll n, ll m) {
  if (m > n) return 0;
  return fac[n] * inv[m] % p * inv[n - m] % p;
}
ll lucas(ll n, ll m) {
  if (n == 0) return 1;
  return lucas(n / p, m / p) * C(n % p, m % p) % p;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  rep(id, 0, 3) {
    p = b[id];
    ll& k = a[id];
    init();
    for (ll i = 1; i * i <= n; i++) {
      if (n % i) continue;
      int j = n / i;
      ll x = lucas(n, i);
      k += x;
      if (j != i) {
        x = lucas(n, j);
        k += x;
      }
    }
    k %= p;
  }
  extcrt();
  ll ans = fastpow(q, a[3], MOD);
  cout << ans;
  return 0;
}